﻿#include <iostream>
#include <queue>
#include <stack> 
#include <vector>
using namespace std;
#define maxPID 10
#define maxDEV 20
int Max[maxPID][maxDEV];//进程与设备
/*int Max[maxPID][maxDEV] = {
	0,0,1,2,1,7,5,0,2,3,5,6,0,6,5,2,0,6,5,6
};*/
int alloc[maxPID][maxDEV];//已分配的进程设备
/*int alloc[maxPID][maxDEV] = {
	0,0,1,2,1,0,0,0,1,3,5,4,0,6,3,2,0,0,1,4
};*/
int need[maxPID][maxDEV];//需要的进程设备
//int need[maxPID][maxDEV] = {
//	0,0,0,0,0,7,5,0,1,0,0,2,0,0,2,0,0,6,4,2
//};
int avail[maxDEV];//可分配的设备
//int avail[maxDEV] = {
//	1,5,2,0
//};
int request[maxPID][maxDEV];//需求
int work[maxDEV];//系统可提供的设备
bool finish[maxPID];//进程完成情况 0 false 1 true
int finishBak[maxPID];//拟分配副本
int n = 0, m = 0;//n 进程号 m 资源号
queue <int> searchQ;//dfs 的所有进程
stack <int> stackPid;
stack <int> ansPid,tmp;
vector <int> vectorPid;
int falseNum = 0;

int safe();
void BakFinish();
int Judge(int pid);
void Bank();
void show();
int main()
{
    Bank();
    cout << "Hello World!\n";
}

void dfs() {
	//结束条件
	if (stackPid.size() == vectorPid.size()) {
		tmp = stackPid;
		return;
	}
	//开始搜索
	for (int i = 0; i < vectorPid.size(); i++) {
		int pid = vectorPid[i];//当前进程
		//cout<<"开始" << pid << endl;
		if (finishBak[pid] == 0) {//当前进程未试过
			bool flag = 1;
			//判断需求是否大于可获得
			for (int j = 0;j < m; j++) {
				if (need[pid][j] > work[j]) {
					flag = 0; break;
				}
			}
			//cout << "flag" << flag << endl;
			if (flag) {
				//如果可以分配，就将finishBak[pid]设为true，进行下个的分配
				finishBak[pid] = true;
				//释放设备
				for (int k = 0; k < m; k++) {
					work[k] += alloc[pid][k];
					//cout << work[i] << " ";
				}
				//cout << endl;
				stackPid.push(pid);//将分配的压入栈
				return dfs();//寻找下个
				//回收设备
				for (int l = 0; l < m; l++)
					work[l] -= alloc[pid][l];
				stackPid.pop();//将分配的弹出栈
				finishBak[pid] = false;
			}
		}
	}
		
}
int safe() {
	int flag = 1;
	while (!vectorPid.empty())
		vectorPid.pop_back();
	//cout << "未完成" << endl;
	for (int i = 0; i < n; i++) {
		//所有未完成的进程入向量
		if (finishBak[i]==0) {
			vectorPid.push_back(i);
			//cout << i << " ";
		}
	}
	//cout << endl;
	//清除上次保存的pid
	while (!stackPid.empty())
		stackPid.pop();
	dfs();
	if (tmp.size() != vectorPid.size())
		flag = 0;
	while (!tmp.empty()) {
		ansPid.push(tmp.top());
		tmp.pop();
	}
	return flag;
}
int Judge(int pid) {
	int flag = 0;
	//资源检查
	for (int i = 0; i < m; i++) {
		if (request[pid][i] > need[pid][i]) {
			flag = 1;
		}
	}
	if (flag) {
		cout << "所请求资源超过需求(need)！" << endl;
		return 0;
	}
	else {
		int avaFlag = 0;
		//资源检查
		for (int i = 0; i < m; i++) {
			if (request[pid][i] > avail[i])
				avaFlag = 1;
		}
		if (avaFlag == 1) {
			cout << "没有足够的资源分配给进程" << pid << "waiting..." << endl;
		}
		else {
			//可以分配设备
			for (int i = 0; i < m; i++) {
				avail[i] -= request[pid][i];//空闲设备
				need[pid][i] -= request[pid][i];//所需减少
				alloc[pid][i] += request[pid][i];//分配增加
			}
			//查看分配后是否完成
			int finishFlag = 1;//1 为完成
			for (int i = 0; i < m; i++)
				if (need[pid][i]) {//有任意一个需求不为0 就是没有完成
					finishFlag = 0;
					break;
				}
			if (finishFlag) {
				//释放资源
				for (int i = 0; i < m; i++) {
					avail[i] += alloc[pid][i];
				}
			}
			finish[pid] = finishFlag;

			//备份finish
			BakFinish();

			//初始化work
			for (int i = 0; i < m; i++)
				work[i] = avail[i];

			//安全性检查算法
			int safeStatue = safe();
			
			//不安全
			if (safeStatue==0) {
				cout << "不存在安全序列" << endl;
				//回收
				if (finish[pid] == 0) {//分配后没有完成
					for (int i = 0; i < m; i++) {
						avail[i] += request[pid][i];
						need[pid][i] += request[pid][i];//所需减少
						alloc[pid][i] -= request[pid][i];//分配增加
					}
				}
				else {//分配后完成
					for (int i = 0; i < m; i++) {
						avail[i] -= alloc[pid][i];//可获得先减少，完成释放的
						avail[i] += request[pid][i];
						need[pid][i] += request[pid][i];//所需还原
						alloc[pid][i]-= request[pid][i];//分配还原
					}
				}
				finish[pid] = 0;
				return 0;
			}
			//安全
			else {
				cout << "存在的安全序列为：";
				while (!ansPid.empty()) {
					cout<<ansPid.top()<<" ";
					ansPid.pop();
				}
				cout << endl;
			}
			if (finish[pid] == 1)
				for (int i = 0; i < m; i++)
					alloc[pid][i] = 0;
			//安全
			cout << "资源已经成功分配给进程，系统处于安全状态." << endl;
			return 1;
		}
	}
}
void BakFinish() {
	for (int i = 0; i < n; i++) {
		finishBak[i] = finish[i];
	}
}
void Bank() {
	//n = 5; m = 4;
	cout << "请输入进程数n和资源种类数m" << endl;
	cin >> n >> m;
	cout << "请输入每个资源现有个数：" << endl;
	for (int i = 0; i < m; i++) {
		cin >> avail[i];
	}
	cout << "请输入每个进程最多所需要的资源数" << endl;
	for (int i = 0; i < n; i++) {
		cout << "进程 " << i << " : ";
		for (int j = 0; j < m; j++) {
			cin >> Max[i][j];
		}
	}
	cout << "请输入每个进程已经分配的资源数" << endl;
	for (int i = 0; i < n; i++) {
		cout << "进程 " << i << " : ";
		for (int j = 0; j < m; j++) {
			cin >> alloc[i][j];
			need[i][j] = Max[i][j] - alloc[i][j];
		}
	}

	for (int i = 0; i < n; i++) {
		int flag = 1;
		for (int j = 0; j < m; j++) {
			if (need[i][j] != 0) {
				flag = 0;//未完成
				break;
			}
		}
		finish[i] = flag;
	}

	show();
	int pid = 0;
	cout << "输入请求资源的进程号pid，结束输入-1"<<endl;
	cin >> pid;
	while (pid != -1) {
		cout << "输入进程 " << pid << " :请求的各种资源数：\n";
		for (int i = 0; i < m; i++) {
			cin >> request[pid][i];
		}
		
		/*安全检查算法*/
		Judge(pid);

		show();
		cout << endl;
		cout << "输入请求资源的进程号pid，结束输入-1" << endl;;
		cin >> pid;
	}

}
void show() {
	cout << "\n资源分配如下：" << endl;
	cout << "\t  max" << "\t   alloc     need" << "\tavail   finish" << endl;
	for (int i = 0; i < n; i++) {
		cout << "进程 " << i << " |";
		for (int j = 0; j < m; j++)
			cout << Max[i][j] << " ";
		cout << "| ";
		for (int j = 0; j < m; j++)
			cout << alloc[i][j] << " ";
		cout << "| ";
		for (int j = 0; j < m; j++)
			cout << need[i][j] << " ";
		cout << "| ";
		for (int j = 0; j < m; j++)
			cout << avail[j] << " ";
		cout << "|    ";
		cout << finish[i]<< "  |"<<endl;
		
	}
}